package org.example.SolutionNew003;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class DoubleTree011 {
    public static void main(String[] args) {
        DoubleTree011 dt=new DoubleTree011();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.left.right = new TreeNode(4);
        root.left.left = new TreeNode(3);
//        root.left.right.right = new TreeNode(3);
        dt.flatten(root);
        System.out.println(root.val);
        System.out.println(root.right.val);
        System.out.println(root.right.right.val);
        System.out.println(root.right.right.right.val);
    }

    //深度+list（扩展就是把深度换成广度遍历）
    public void flatten1(TreeNode root) {
        //没有明确思路，试一下先序遍历，存node再连接
        if(root==null) return;
        List<TreeNode> list=new ArrayList<>();
        preOrderTheTree(root,list);
        TreeNode dummy=new TreeNode();
        TreeNode cur=dummy;
        for(int i=0;i<list.size();i++){
            list.get(i).left=null;
            cur.right=list.get(i);
            cur=cur.right;
        }
    }

    public void preOrderTheTree(TreeNode root,List<TreeNode> list){
        if(root==null) return;
        list.add(root);
        preOrderTheTree(root.left,list);
        preOrderTheTree(root.right,list);
    }

    //广度+提前保存右边节点防止丢失
    public void flatten2(TreeNode root) {
        if(root==null) return;
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        TreeNode prev=null;

        while(!stack.isEmpty()){
            TreeNode cur=stack.pop();
            if(prev!=null){
                prev.left=null;
                prev.right=cur;
            }
            TreeNode left=cur.left,right=cur.right;
            if(right!=null){
                stack.push(right);
            }
            if(left!=null){
                stack.push(left);
            }
            prev=cur;
        }
    }

    //一个节点左子树的最右节点是这个节点右子树的最左节点的前一个节点
    //找到以后，再另该节点的左边置空，右边为其左子树最左的节点即可
    public void flatten(TreeNode root) {
        if(root==null) return;
        TreeNode cur=root;
        while(cur!=null){
            if(cur.left!=null){
                TreeNode next=cur.left;
                TreeNode predecessor=next;
                while(predecessor.right!=null){
                    predecessor=predecessor.right;
                }
                predecessor.right=cur.right;
                cur.left=null;
                cur.right=next;
            }
            cur=cur.right;
        }
    }
}
